package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/10/11 16:53
 **/
public class Day39_2_Num204_CountPrimes {
    class Solution {
        public int countPrimes(int n) {
            int ans = 0;
            int[] arr = new int[n];
            for(int i = 2; i < n; ++i)
                arr[i] = 1;
            for(int i = 2; i < n; ++i){
                if(arr[i] == 1){
                    ans++;
                    for(int j = 2 * i; j < n; j += i)
                        arr[j] = 0;
                }
            }
            return ans;
        }
    }
}